package LinkedList;//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,2,1]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：head = [1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围[1, 10⁵] 内 
// 0 <= Node.val <= 9 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 栈 递归 链表 双指针 👍 1167 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Stack;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class isPalindrome {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    }
    public static boolean isPalindrome(ListNode head) {
        /**
         * 1.反转链表
         * 找到中间位置节点，截取后反转
         * 反转后的后面链表和前面的链表一一进行比较即可
         * */
        ListNode nHead = head;
        int len = 0;
        //先计数
        while(nHead != null){
            len++;
            nHead = nHead.next;
        }
        //处理特殊情况
        if (len<2){
            return true;
        }
        nHead = head;  //还原
        /**
         * 截链表
         * 如果链表长度为奇数，则需要截取两边的，中间的扔掉即可
         * 如果为偶数，则从中间点，截取为两个
         * */
        ListNode pre = head;
        ListNode A = pre;
        ListNode B = null; // 第二段的头
        // 保证移动到要截取点的前一个位置
        for (int i = 0; i < len / 2 - 1; i++) {
            pre = pre.next;
        }
        //确定第二段的头
        if (len % 2 == 0){
            B = pre.next;
        }else{
            B = pre.next.next;  //跳过最中间的节点
        }
        pre.next = null;  //第一段的后面截断
        //反转第二段链表
        B = reverseList(B);
        //判断值
        while(A != null && B != null){
            if(A.val != B.val){
                return false;
            }
            A = A.next;
            B = B.next;
        }
        return true;

    }
    static ListNode reverseList(ListNode head) {

        /**
         *  递归反转
         * 若此时 nk->nk+1 我们希望 nk+1的下一个节点指向 nk
         *  即nk+1->nk 则 nk.next.next = nk
         * */
        //递归结束条件
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public boolean isPalindrome1(ListNode head) {
        /**
         * 2.利用栈
         * */
        Stack<Integer> stack = new Stack<>();
        ListNode nHead = head;
        int len = 0;
        // 遍历一遍链表的同时，计算长度，将值添加到栈中
        while(nHead!=null){
            len++;
            stack.push(nHead.val);
            nHead = nHead.next;
        }
        nHead = head;
        // 然后从头遍历一半，栈弹出一半依次比较,需注意奇偶
        for (int i = 0; i < len / 2; i++) {
            if(nHead.val != stack.pop()){
                return false;
            }
            nHead = nHead.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode n1 = new ListNode(2);
        ListNode n2 = new ListNode(3);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(1);
        head.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        System.out.println(isPalindrome(head));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
